package pers.vic.basics.leetcode;

import java.util.Stack;

/**
 * @author Vic.xu
 * @description:32. 最长有效括号 {@literal https://leetcode-cn.com/problems/longest-valid-parentheses/}
 * @date: 2020/11/23 11:40
 */
public class J0032_H_LongestValidParentheses {
    /*
    给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
    (() → 2
    )()()) → 4
     */

    /**
     * 大体思路：什么动态规划的 还是找不到规律 我先来一手暴力操作
     * 写完了居然一次性通过，这是我第一次hard，不看题解，自己瞎写却一次通过的
     * <p>
     * 1. 从前往后读取，遇到‘)’则判断它是否匹配的，同时把上一个能配置成功的‘(’ 均标记为 匹配成功
     * 2. 寻找最大连续匹配成功
     * </p>
     *
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        char[] cs = s.toCharArray();
        //记录每个下标位置是否匹配
        int[] matchs = new int[cs.length];
        //入栈 记录的是 字符的下标
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < cs.length; i++) {
            //入栈
            Character cur = cs[i];
            if ('(' == cs[i]) {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    int matchIndex = stack.pop();
                    matchs[matchIndex] = 1;
                    matchs[i] = 1;
                }
            }
        }
        //找出连续最长的匹配 也即嘴脸的连续的1
        int max = 0;
        int temp = 0;
        for (int i = 0; i < matchs.length; i++) {
            if (matchs[i] == 1) {
                temp++;
                max = max > temp ? max : temp;
            } else {
                temp = 0;
            }
        }
        return max;
    }

    /**
     * 动态规划解法
     * <p>
     * 三步走起：
     * 1.记录什么状态：dp[i] :当前下标记录最长的有效括号长度， 只应对应 右括号')'
     * 2. 状态方程：参见代码
     * 3. 状态初始化
     *
     * </p>
     * <p>
     * ()(())()
     * 01234567
     * [1] = 2
     * [2] = 0
     * [3]=0
     * [4] = 2 + dp[2] = 2
     * [5] = 2 + [4] + [1] = 6  跳过中间的连续匹配位置[5-1] = 2的   下标后是 再加上前一个位置d 匹配数[5-2-2] = 2 ：dp[5] = 2+ dp[5-1] + dp[5-dp[5-1]-2] = 6
     * [6] = 0
     * [7] = 2 + [6] = 8
     */
    public static int longestValidParentheses2(String s) {
        int max = 0;
        int len = s.length();
        //当i对应为右括号的时候 dp[i]表示到i位置的最长有效括号数，
        int[] dp = new int[len];
        char[] cs = s.toCharArray();
        for (int i = 1; i < len; i++) {
            if (')' == cs[i]) {
                //判断上一个位置是否是对应的‘(’
                if (cs[i - 1] == '(') {
                    int preLen = i - 2 > 0 ? dp[i - 2] : 0;
                    dp[i] = preLen + 2;
                    max = Math.max(max, dp[i]);
                    //跳过之前匹配的记录数  判断其前一个是否是 '(' ，判断完毕之后再往前一个是否是连续匹配
                } else {
                    //前一个')'连续匹配的长度
                    int preLen = dp[i - 1];
                    int preIndex = i - preLen -1;
                    //跳过中间的连续长度之后依然能匹配上
                    if (preIndex >= 0 && cs[preIndex] == '(') {
                         //继续加上   cs[preIndex]   之前的连续长度
                        int prePreLen = preIndex  >= 1 ? dp[preIndex -1] : 0;
                        dp[i] = 2 + preLen + prePreLen;
                    }
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }


    public static void main(String[] args) {
        String s = "()(())()";
        System.out.println(longestValidParentheses(s));
        System.out.println(longestValidParentheses2(s));
    }
}
